package com.jacky.二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 二叉树的锯齿形层序遍历_103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //如果二叉树根节点为null,直接返回List
        if(root == null) return new ArrayList<>();
        //定义一个返回值
        List<List<Integer>> res = new ArrayList<>();
        //定义一个链表队列，用来辅助层次遍历
        Queue<TreeNode> queue = new LinkedList<>();
        //把跟节点放到队列里面
        queue.add(root);
        //定义一个是否从左到右遍历的标记
        boolean isLeftToRight=true;
        //如果队列不为空，就开始遍历
        while(!queue.isEmpty()){
            //定义一个数组队列，用来存储二叉树每一层的遍历结果
            List<Integer> list = new ArrayList<>();
            //获得队列大小
            int size = queue.size();
            //遍历二叉树的每一层
            for(int i=0;i<size;i++){
                TreeNode cur = queue.poll();
                if(isLeftToRight){
                    //从左到右，尾插法
                    list.add(cur.val);
                }else{
                    //从右到左，头插法
                    list.add(0,cur.val);
                }
                //如果当前节点有左子树，则入队列
                if(cur.left != null) queue.add(cur.left);
                //如果当前节点有右子树，则入队列
                if(cur.right != null) queue.add(cur.right);
            }
            //遍历完一层之后，把结果放到list
            res.add(list);
            //更换遍历方向
            isLeftToRight = !isLeftToRight;
        }
        return res;
    }
}
